class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if(len < 2) return s;
        vector<vector<int>> dp(len, vector<int>(len));
        int begin = 0;
        int maxLen = 1;
        for(int L = 2;L <= len;L++){
          for(int i = 0;i < len;i++){
            int j = L + i -1;
             if(j >= len) {
               break;
             }
            if(s[i] == s[j]){
              if(j - i < 3){
                dp[i][j] = true;
              }else{
                dp[i][j] = dp[i+1][j-1];
              }
            }else{
              dp[i][j] = false;
            }
            if(dp[i][j] &&j - i + 1 > maxLen){
               maxLen = j - i + 1;
               begin = i;
            }
          }
        }
        return s.substr(begin , maxLen);
    }
};
